package com.zk.algorithm.linkedlist;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.ListNode;

/**
 * 是否有环
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
public class LinkedListCycle {

    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;

        ListNode walker = head;
        ListNode runner = head;

        // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
        //      ↑
        //   walker
        //                ↑
        //             runner
        while (runner.next != null && runner.next.next != null) {
            walker = walker.next;
            runner = runner.next.next;

            if (walker == runner)
                return true;
        }

        return false;
    }

}
